§ 1.1 Field of the Invention
The invention concerns detecting and diagnosing errors in connections, such as multi-protocol label switching (MPLS) label-switched paths (LSPs), that prevent user traffic from being delivered, or from being delivered in a reliable or timely manner.
§ 1.2 Description of Related Art
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art.
Circuit-switched networks establish a connection between hosts (e.g., parties to a communication) for the duration of their communication or call. Because the circuit is kept up for the duration, bandwidth is wasted when data is not being transferred on the circuit. To avoid wasted bandwidth during times when no data is being transferred, packet-switched networks may be used. Packet-switched networks forward addressed data (referred to as “packets” in the specification below without loss of generality), typically on a best efforts basis, over shared links from a source to a destination. Packet-switched networks are made up of interconnected nodes (referred to as “routers” in the specification below without loss of generality). The routers may be geographically distributed throughout a region and connected by links (e.g., optical fiber, copper cable, wireless transmission channels, etc.). In such a network, each router typically interfaces with (e.g., terminates) multiple links.
Packets traverse the network by being forwarded from router to router until they reach their destinations (typically specified by layer-2 or layer-3 addresses in the packet headers). Unlike circuit switches which establish a connection for the duration of a call to send data received on a given input port out on a given output port, routers examine the destination addresses of received packets and, based on these destination addresses, determine the appropriate link on which to send them.
In some cases, it may be considered desirable to establish a fixed path through at least a part of a packet-switched network for at least some packets. For example, traffic engineering permits network administrators to map traffic flows onto an existing physical topology so that traffic flows can be moved away from congested paths to one or more less congested paths. Alternatively, paths can be determined autonomously, even on demand. Label-switching can be used to establish a fixed path from a head-end node (e.g., an ingress router) to a tail-end node (e.g., an egress router). The fixed path may be determined using known protocols. Once a path is determined, each router in the path may be configured (manually, or via some signaling mechanism) to forward packets to a peer (e.g., a “downstream” or “upstream” neighbor) router in the path. Routers in the path determine that a given set of packets (e.g., a flow) are to be sent over the fixed path, as opposed to being routed individually, based on unique labels added to the packets.
Another use of label-switching is to create “tunnels” through a network such that once a packet enters a tunnel, the packet is forwarded to the tunnel endpoints independent of the packet's original headers. Only the ingress router looks at the packet headers and determines which subset of packets get sent into which tunnels. Intermediate (also referred to as “transit”) routers use just the labels to forward the packet. This is useful in many applications, such as Virtual Private Networks (VPNs) or Layer 2 circuits. Such tunnels may be point-to-point, point-to-multipoint, multipoint-to-point, or multipoint-to-multipoint.
The tunnel generated may be an LSP. More specifically, the operation of forwarding a packet, based on address information, to a next hop can be thought of as two steps—partitioning the entire set of possible packets into a set of forwarding equivalence classes (FECs), and mapping each FEC to a next hop. As far as the forwarding decision is concerned, different packets which get mapped to the same FEC are indistinguishable. With MPLS, a particular packet is assigned to a particular FEC just once, as the packet enters the label-switched domain. The FEC to which the packet is assigned is encoded as a label, typically a short, fixed length value. Thus, at subsequent nodes, no further header analysis is needed—all subsequent forwarding over the label-switched domain is driven by the labels. Such FECs may be generalized such that particular ports, wavelengths, time slots, channels, etc. are used instead of, or encoded by, labels.
“Failures” in a Label-Switched Path
Unfortunately, forwarding information (such as an “OUT” label) of the forwarding component of label-switching routers (LSRs) may become corrupted. Consequently, data leaving such an LSR will be “black-holed” or mis-routed. When a next LSR in the LSP receives the packet with the wrong label, it will either discard it or transmit the packet along an LSP other than the desired LSP.
Since the control plane of routers may use Internet protocol (IP) addresses to route its messages, the control plane will likely still be active and therefore might not recognize the error. Consequently, an ingress LSR may continue to transmit data through the non-functioning LSP.
If an ingress LSR continuously fails to deliver data through a given LSP, that LSP may be suspected of being down. It is desirable to be able to detect, within a reasonable amount of time, if a suspected LSP is actually down. In the art, there is no practical and quick solution known to detect the liveliness of the data plane of an LSP. Presently, if an LSP is suspected of being down, users perform manual memory dumps along several LSPs, examining the labeling information of the control plane and the data plane of the LSPs, to discover which LSP was not functioning properly. This procedure can be very time consuming and may not be a practical solution because of the length of time needed to locate the problem. It may also be desirable to monitor an LSP before it is even suspected of being down.